This invention relates to artificial intelligence production systems, and more particularly, to a method for uniting a sequence of changes to working memory objects of such a system, while deferring matching of the working memory to system rules.
Rule-based artificial intelligence production systems signify computer programs written in a production system language. A production system generally includes working memory including a set of elements, a set of rules defined in terms of the elements, and a control mechanism, or inference engine, which executes the rules with reference to the elements. The control mechanism matches the rules with the elements to produce a conflict set consisting of rules associated with matched elements. The control mechanism resolves the conflict set by selecting the order with which the rules are executed, and "fires" the rules.
Rule-based artificial intelligence production systems are known, as are languages which support their construction. Reference is given to: Brownston et al. "Programming Expert Systems in OPS5", Addison-Wesley, copyright 1985; Jackson, "Introduction to Expert Systems", Addison-Wesley, copyright 1986; Forgy, "OPS5 User's Manual", CMU-CS-81-135, copyright 1981; and Forgy, "RETE: A Fast Algorithm For the Mini Pattern/Mini Object Pattern Match Problem", Artificial Intelligence, Vol. 19, copyright 1982.
Brownston describes a rule-based artificial intelligence production system ("production system") based upon a cycle of three states including matching-rule, select-rule, execute-rule. Brownston points out that the matching of elements to rules is the primary inefficiency in the operation of a production system. The speed of the inference engine of any such system is enhanced by a reduction in the matching phase of the operation.
The matching phase in a language such as OPS5 is performed by a patterned network which systematizes the association of system elements with the system rules to select which rules are ready for execution. The matching algorithm utilized in OPS5 is called the RETE method. The RETE matching procedure is well known, having been described, for example, in Forgy's Artificial Intelligence article. Rules (or "productions" or "production rules") have two parts, the LHS (left-hand side, or if-part) and the RHS (right-hand side, or then-part). Relatedly, a rule can be considered an if-then statement of the form:
If conditions A, B, C are true, then take actions X, Y, Z.
In a production system, the working memory (WM) forms the universal data base of the system. Characteristically, the WM is segmented into classes, the classes consisting of elements, or members, each member being referred to as a class member (CM). Each rule of the rule set has the two parts described above: LHS and RHS. The LHS is a logical expression referring to working memory classes, and the RHS is a list of operations to be performed on CMs.
The inference engine is the control mechanism that selects rules to fire and then executes the actions of the RHS of a selected rule, repeating the cycle. The satisfied rules are called instantiations. An instantiation consists of the rule and list of CMs that satisfy the rule's LHS. The inference engine "fires" an instantiation by executing the RHS of the rule, using the list of CMs in the instantiation. The set of all instantiations available for firing is called the conflict set. The inference engine conducts a procedure called conflict resolution to select the instantiation from the conflict set to fire next. The firing of a rule by execution of its RHS can create, change, or delete elements in WM and lead to changes of the conflict set. The inference engine of a rule-based production system repeatedly executes, in a cycle, the step of recognizing all instantiations in the conflict set, the step of resolving which instantiation of the step to fire, and the set of firing the selected instantiation. The cycle is called the "recognize-act" cycle.
Upon the firing of each rule, the inference engine again determines the conflict set by computing using the RETE algorithm. The RETE algorithm is expressed as a sorting network. The LHS conditions of all rules in the rule set are compiled into a sorting network including nodes, most of which are associated with tests. Use of the network to recognize instantiations is called "RETE" or "match" processing. In RETE processing, tokens are passed through the network. Tokens that traverse through the network represent instantiations in or for the conflict set. RETE processing is computationally expensive, amplifying the importance of production system techniques that reduce it.
Early rule-based production systems supported only a fixed sequence of actions in the RHS of a rule. This restriction led to very short RHSs. This rudimentary form of the RHS resulted in rules which rarely would make more than one change to the same CM during one firing. The increasing use of high-level procedural language techniques for writing rules has led to the incorporation of procedures such as subroutines, functions, and coroutines in rule RHSs. In these cases, during the execution of a rule RHS where a high-level procedural language is used, the execution of a procedure, and the nesting of these frequently result in repeated changes to a single CM in the execution of one RHS. As an example, suppose that in executing a RHS, a subroutine is called. It is asserted that the program language allows for the subroutine to be written using rule-based production system techniques. During execution of the subroutine many rules may fire, and in completing the subroutine's computations, many CMs may be created, changed repeatedly, and then deleted from working memory before return is made to the parent routine and execution proceeds for the RHS that called the subroutine.
Customarily, it is standard to undertake RETE processing immediately upon the making of any change to a CM. Therefore, the computational intensity--and expense--of a production system will only be amplified by elaboration of RHS capability which permits compound actions and supports hierarchical routine execution.